package LearnAlgorithm.i_递归进阶andDFSand剪枝and回溯;

import java.util.HashSet;
import java.util.Set;

public class d合法括号 {
	public static void main(String[] args) {
		d合法括号 test = new d合法括号();
		Set<String> res1 = test.parenthesis(3);
		System.out.println(res1);
		Set<String> res2 = test.parenthesis2(2);
		System.out.println(res2);
	}
	
	/**
	 * 迭代形式
	 * @param n
	 * @return
	 */
	public Set<String> parenthesis2(int n) {
		Set<String> res = new HashSet<String>();//保存状态的集合；也是最终输出的结合
		res.add("()");
		if (n == 1) {//特殊情况，n==1
			return res;
		}
		for (int i = 2; i <= n; i++) {
			Set<String> helper = new HashSet<String>();
			for (String elementOfRes : res) {
				helper.add(elementOfRes + "()");
				helper.add("()" + elementOfRes);
				helper.add("(" + elementOfRes + ")");
			}
			res = helper;//保存上一次迭代状态
		}
		return res;
	}
	
	/**
	 * 递归形式
	 * @param n
	 * @return
	 */
	public Set<String> parenthesis(int n) {
		Set<String> s_n = new HashSet<String>();
		if (n == 1) {//出口
			s_n.add("()");
			return s_n;
		}
		Set<String> s_n_1 = parenthesis(n - 1);
		for (String elementOfN_1 : s_n_1) {
			s_n.add("()" + elementOfN_1);
			s_n.add(elementOfN_1 + "()");
			s_n.add("(" + elementOfN_1 + ")");
		}
		return s_n;
	}
}
